This invention relates to correlation, especially for synchronizing to long number sequences in communications systems such as spread spectrum cellular systems or other wireless digital communications systems. The long number sequences are typically pseudo random noise sequences, generally referred to as PN sequences.
In spread spectrum communications systems, such as CDMA (code division multiple access) wireless communications systems, fast synchronization to a PN sequence is of increasing importance. It is known to use correlation techniques for PN sequence synchronization, this also being referred to as PN acquisition. Typically, a receiver of the communications system receives a communicated signal incorporating a PN sequence and correlates this with locally generated versions of the PN sequence using different time shifts, determining a maximum correlation result and hence a corresponding time shift for PN synchronization purposes. However, for long PN sequences the computation required for the correlation becomes so extensive that it becomes difficult to implement using either DSP (digital signal processing) techniques or dedicated hardware devices.
For example, the PN sequence may be a maximal length or m-sequence which is generated by a linear feedback shift register and whose length is 2rxe2x88x921 symbols where r is the number of stages of the shift register. In wireless CDMA communications systems such as those commonly referred to by the designations IS-95 and CDMA2000, for example r=42, so that the length of the PN sequence is very large, and a large number of correlations with candidate PN sequence timings must be carried out. It is desired in such systems to complete the PN sequence synchronization within one frame of 20 ms duration, so that the computations for such correlations must be performed very quickly. This onerous computation requirement presents an increased problem for the case of packet data communications using such communications systems, for which the PN sequence synchronization must be performed for every packet.
Accordingly, an object of this invention is to provide an improved correlation method for facilitating fast synchronization to a long PN sequence.
One aspect of this invention provides a method of correlating a first symbol sequence with a relatively large number of second symbol sequences to produce respective correlation results for a correlation block of symbols, comprising the steps of: for each of a plurality of sub-blocks of the correlation block, producing respective sub-block correlation results; and accumulating the respective sub-block correlation results to produce the respective correlation results for the correlation block; wherein the step of producing respective sub-block correlation results comprises, for each sub-block, the steps of: correlating the sub-block of the first symbol sequence with all possible sequences for the sub-block of the second symbol sequences to produce a plurality of possible correlation results for the sub-block; and for each of the second symbol sequences, selecting a respective one of the possible correlation results for the sub-block, to constitute the sub-block correlation result for the respective second symbol sequence, in dependence upon the sub-block of the respective second symbol sequence.
If the correlation block length is L symbols and each of the sub-blocks comprises k symbols, where L=mk and L, k, and m are integers greater or equal to one, preferably each of the second symbol sequences is a binary symbol sequence and the step of correlating each sub-block of the first symbol sequence with all possible sequences for the sub-block of the second symbol sequences produces 2k possible correlation results for the sub-block.
Each of the second symbol sequences can be provided from a pseudo random noise sequence, and the first symbol sequence can be derived from a received signal of a wireless communications system. The method can further comprise the step of detecting a maximum of the correlation results for the correlation block thereby to identify one of said second symbol sequences providing the maximum correlation result.
Another aspect of this invention provides a correlation arrangement comprising: 2k correlators each for correlating k symbols of a first symbol sequence with a respective one of 2k different sequences each of k binary symbols to produce a respective one of 2k correlator outputs; N selectors each responsive to k symbols of a respective one of N binary symbol sequences to select a respective one of said 2k correlator outputs; and N accumulators each for accumulating the selected correlator outputs of a respective one of the N selectors for a plurality of m successive selected correlator outputs to produce a respective one of N correlation results for a correlation block of mk symbols; where k, N, and m are integers greater or equal to one.
The correlation arrangement can further comprise a detector responsive to the N correlation results to identify one of the N binary symbol sequences providing a maximum correlation result.
The invention also extends to a wireless communications system receiver including a correlation arrangement as recited above, wherein the first symbol sequence is derived from a received signal of the system.